The present invention relates to an error correcting coding method used with the recording/reproducing apparatus.
The Reed-Solomon code is used for the recording/reproducing apparatus such as the magnetic disk device, the magneto-optic disk device and the compact disk device. The magnetic disk device uses the Reed-Solomon code on the finite field GF(28) including 28 elements which is a set wherein the four rules of arithmetic are defined (except for xe2x80x9cdivision by 0xe2x80x9d) mutually by the elements, where GF is an abbreviation of Galois Field. The error correcting coding and the error correcting process for the recording/reproducing apparatus are performed with eight bits of the Reed-Solomon code as one symbol providing a unit for calculation.
In the Reed-Solomon code, it is known that the code having the maximum number t of correction symbols can be configured by setting the number of redundant symbols to 2t. The length of the sector providing a unit for performing each recording/reproducing operation is 512 symbols. In view of the fact that the length of the Reed-Solomon code that can be configured on GF(28) is 255 (=28xe2x88x921) symbols or less, data are divided (interleaved) into three or more blocks and then an error correcting code is provided for each block.
One of the advantages of the Reed-Solomon code is that the symbol positions for calculation are arranged, from the most significant place of the code, as xcex1n-1, xcex1n-2, . . . , xcex12, xcex11, xcex10 (xcex1: primitive root of finite field), so that the symbol position for calculation can be regularly calculated by the multiplier alone at the time of the Chien search for the error position for decoding. The Chien search is a method for searching for a solution of an equation by substituting the elements into the equation sequentially.
Consider the case in which the Reed-Solomon code on GF(28) is used for a recording system of 512 symbols per sector. In view of the fact that the code length is not more than 28xe2x88x921=255 symbols and the relation holds that 512/255 greater than 2, the problem is that the number of interleaves cannot be reduced below 3.
As long as the maximum number of correction symbols per sector is constant, the smaller the number of interleaves, the higher the error correcting ability of the code.
With the error correcting coding method according to this invention, an elliptic code on GF(2m) is used to configure a code longer than 2mxe2x88x921 and therefore the number of interleaves can be reduced.
For configuring the code having the maximum number t of correction symbols by the elliptic code, the number of redundant symbols is set to 2t+1. The number of redundant symbols for this code is 287xe2x88x92256=31, and therefore the maximum number of correction symbols is given as 15 (15xc3x972+1=31). The use of this code makes it possible to configure 512 bytes per sector in two interleaves. The principle of the error correcting coding method according to this invention will be explained below.
Assume that E(C, GF(2m)) for the elliptic curve C: y2+a1xy+a3y+a0x3+a2x2+a4x+a6=0 on GF(2m) indicates the following set, xcex5 is the number of elements of E (C, GF (2m)) and a0, a1, a2, a3, a4, a6 are constants.
E(C, GF(2m))={(xcex1, xcex2)xcex5GF(2m)2|xcex22+a1xcex1xcex2+a3xcex2+a0xcex13+a2xcex12+a4xcex1+a6=0}xe2x80x83xe2x80x83(1)
∪{o: point at infinity}
where if the points associated with E(C, GF(2m)) {o} are assigned the numbers p(1), p(2), . . . , p(xcex5xe2x88x921), the code word of the elliptic code is defined as a column vector w satisfying Hw=0 for the matrix H of equation (2).                               H          =                                    (                              h                                  i                  ,                  j                                            )                                                      1                ≤                i                ≤                                  n                  -                  k                                                            1                ≤                j                ≤                n                                                    ,                              h                          i              ,              j                                =                                    v                              i                -                1                                      ⁡                          (                              P                                  (                  j                  )                                            )                                      ,                  
                ⁢                  (                                                                                                                                        v                        0                                            ⁡                                              (                                                  x                          ,                          y                                                )                                                              =                    1                                    ,                                                                                    v                        1                                            ⁡                                              (                                                  x                          ,                          y                                                )                                                              =                    x                                    ,                                                                                    v                        2                                            ⁡                                              (                                                  x                          ,                          y                                                )                                                              =                    y                                    ,                                                                                                                          v                                          j                      +                      2                                                        =                                                                                                              v                          1                                                ⁡                                                  (                                                      x                            ,                            y                                                    )                                                                    ⁢                                                                        v                          j                                                ⁡                                                  (                                                      x                            ,                            y                                                    )                                                                    ⁢                                              xe2x80x83                                            ⁢                      for                      ⁢                                              xe2x80x83                                            ⁢                      j                                        ≥                    1                                                                                )                                    (        2        )            
Especially, the code length n coincides with xcex5xe2x88x921. The elliptic curve C which satisfies the relation n greater than 2mxe2x88x921 can be found by total search of the values of the coefficient aj.
With the definition of equation (2), however, the code word cannot be calculated by other than the method of solving an equation, and therefore the process is very complicated. The calculation can be facilitated by regular matrix operation of the code word by rewriting the equation (2) as follows.
Specifically, assume that the vector with k symbols arranged in column before coding is w0. When H satisfies equation (3), Gw0 constitutes a code word for the matrix G of equation (4). As a matter of fact, the relation is obtained that H(Gw0)=Mxe2x88x921(MH) (Gw0)=Mxe2x88x921((MH)G)w0=0.
∃M: square matrix s.t. MH=(H1|I)xe2x80x83xe2x80x83(3)                     G        =                  [                      I                          H              1                                ]                                    (        4        )            
, where I represents an identity matrix. If H1 can be calculated from equation (5), the redundant symbol of the corresponding code word Gw0 can be calculated from w0.                               Gw          0                =                                            [                              I                                  H                  1                                            ]                        ⁢                          w              0                                =                      [                                          w                0                                                              H                  1                                ⁢                                  w                  0                                                      ]                                              (        5        )            
Equation (6) can be obtained from equation (3). As long as M is calculated and stored in advance, therefore, H1 can be calculated. Thus, the redundant symbol of the code word Gw0 can also be calculated from w0.                                           H            1                    =                                    (                              h                                  i                  ,                  j                                *                            )                                                                        1                  ≤                  i                  ≤                                      n                    -                    k                                                  ,                                            1                ≤                j                ≤                k                                                    ,                              h                          i              ,              j                        *                    =                                    v                              i                -                1                                      ⁡                          (                              P                                  (                  j                  )                                            )                                      ,                  
                ⁢                              (                                                                                                      V                      0                                        ⁡                                          (                                              x                        ,                        y                                            )                                                                                                                                                              V                      1                                        ⁡                                          (                                              x                        ,                        y                                            )                                                                                                                    ⋮                                                                                                                        V                                              n                        -                        k                        -                        1                                                              ⁡                                          (                                              x                        ,                        y                                            )                                                                                            )                    =                      M            ⁡                          (                                                                                                                  v                        0                                            ⁡                                              (                                                  x                          ,                          y                                                )                                                                                                                                                                                v                        1                                            ⁡                                              (                                                  x                          ,                          y                                                )                                                                                                                                  ⋮                                                                                                                                      v                                                  n                          -                          k                          -                          1                                                                    ⁡                                              (                                                  x                          ,                          y                                                )                                                                                                        )                                                          (        6        )            
In order to give the regularity to E(C, GF(2m)) {o}, an arithmetic circuit for realizing the calculation +0 as defined in equation (7) is built in and used.
O+oP=P+oO=P for Pxcex5E(C,GF(2m)),
(x1,y1)+o(x1,y1+a1x1+a3)=0,
(x1,y1)+o(x2,y2)=(x3,y3) (x1xe2x89xa0x2 or y2xe2x89xa0y1+a1x1+a3)
                    {                                                                                                  x                    3                                    =                                                            λ                      2                                        +                                                                  a                        1                                            ⁢                      λ                                        +                                          a                      2                                        +                                          x                      1                                        +                                          x                      2                                                                      ,                                                                                                                              y                    3                                    =                                                                                    (                                                  λ                          +                                                      a                            1                                                                          )                                            ⁢                                              x                        3                                            ⁢                                              "LeftBracketingBar"                        ν                        "RightBracketingBar"                                                              -                                          a                      3                                                                      ,                                                                                        {                                                                                                                              λ                          =                                                                                                                    x                                1                                2                                                            +                                                              a                                4                                                            +                                                                                                a                                  1                                                                ⁢                                                                  y                                  1                                                                                                                                                                                                                      a                                  1                                                                ⁢                                                                  x                                  1                                                                                            +                                                              a                                3                                                                                                                                    ,                                                                                                            xe2x80x83                                                                                                                                                ν                        =                                                                                                            x                              1                              3                                                        +                                                                                          a                                1                                                            ⁢                                                              x                                1                                                                                      +                                                                                          a                                3                                                            ⁢                                                              y                                1                                                                                                                                                                                                        a                                1                                                            ⁢                                                              x                                1                                                                                      +                                                          a                              3                                                                                                                                                                                          (                                                                              x                            1                                                    =                                                                                                                    x                                2                                                            ⁢                                                              xe2x80x83                                                            ⁢                              and                              ⁢                                                              xe2x80x83                                                            ⁢                                                              y                                2                                                                                      ≠                                                                                          y                                1                                                            +                                                                                                a                                  1                                                                ⁢                                                                  x                                  1                                                                                            +                                                              a                                3                                                                                                                                    )                                                                                                                                                                    {                                                                                                                              λ                          =                                                                                                                    x                                1                                3                                                            +                                                              a                                4                                                            +                                                                                                a                                  1                                                                ⁢                                                                  y                                  1                                                                                                                                                                                                                      a                                  1                                                                ⁢                                                                  x                                  1                                                                                            +                                                              a                                3                                                                                                                                    ,                                                                                                            xe2x80x83                                                                                                                                                ν                        =                                                                                                            x                              1                              3                                                        +                                                                                          a                                4                                                            ⁢                                                              x                                1                                                                                      +                                                                                          a                                3                                                            ⁢                                                              y                                1                                                                                                                                                                                                        a                                1                                                            ⁢                                                              x                                1                                                                                      +                                                          a                              3                                                                                                                                                                                          (                                                                              x                            1                                                    ≠                                                      x                            2                                                                          )                                                                                                                                                    (        7        )            
For the element P of E(C, GF (2m)), P +0, . . . , +0P (involving Ps in the number of m) is expressed as [m] P.
The recording/reproducing apparatus according to this invention based on the aforementioned principle is for recording in a recording medium the interleaved data with an error correcting code added thereto and reproducing the recorded data from the recording medium, the apparatus comprising an error correcting decoding circuit for generating an error correcting code using an elliptic code on a finite field GF(2m) (m: positive integer).